<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
    <link type="text/css" rel="stylesheet" href="reset.css"/>
    <script src="https://cdn.bootcss.com/jquery/1.12.4/jquery.min.js"></script>
</head>
<body>
<div id="canvasWrap" style="position: relative; margin:0 auto">


</div>

<div>
    <button type="button" class="J_settype" data-type="2">设置起点</button>
    <button type="button" class="J_settype" data-type="3">设置终点</button>
    <button type="button" class="J_settype" data-type="1">设置路障</button>
    <button type="button" class="J_settype" data-type="0">清除指定路障</button>
    <button type="button" class="J_cal">计算最短</button>
</div>
<script>
    //
    const SIZE = 40;
    let Square = (function () {

        let Square = function (x, y, size) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.type = 0;// 0 平 1.块 2.起 3.终
            this.routeType = [];
        };


        Square.prototype.drawSquare = function drawSquare(ct) {
            ct.save();
            ct.translate(this.x * this.size, this.y * this.size);
            ct.lineWidth = "1";
            ct.strokeStyle = "#000000";
            ct.fillStyle = "#a19ea6";
            ct.beginPath();
            ct.fillRect(0, 0, this.size, this.size);
            ct.rect(0, 0, this.size, this.size);
            ct.closePath();
            ct.stroke();
            ct.restore();


            if (this.type == 2) {
                ct.save();
                ct.translate(this.x * this.size, this.y * this.size);
                ct.fillStyle = "#40cb91";
                ct.strokeStyle = "#40cb91";
                ct.beginPath();
                ct.arc(this.size / 2, this.size / 2, this.size / 2.5 - 5, 0, 2 * Math.PI);
                ct.closePath();
                ct.fill();
                ct.restore();
            } else if (this.type == 3) {
                ct.save();
                ct.translate(this.x * this.size, this.y * this.size);
                ct.fillStyle = "#cb1820";
                ct.strokeStyle = "#cb1820";
                ct.beginPath();
                ct.arc(this.size / 2, this.size / 2, this.size / 2.5 - 5, 0, 2 * Math.PI);
                ct.closePath();
                ct.fill();
                ct.restore();
            } else if (this.type == 1) {
                ct.save();
                ct.translate(this.x * this.size, this.y * this.size);
                ct.lineWidth = "1";
                ct.fillStyle = "#e2a347";
                ct.beginPath();
                ct.fillRect(0, 0, this.size, this.size);
                ct.rect(0, 0, this.size, this.size);
                ct.closePath();
                ct.stroke();
                ct.restore();
            }

            for (let i = 0; i < this.routeType.length; i++) {
                if (this.routeType[i] == 2) {
                    ct.save();
                    ct.translate(this.x * this.size, this.y * this.size);
                    ct.beginPath();
                    ct.lineWidth = "3";
                    ct.strokeStyle = "#e21609";
                    ct.moveTo(this.size / 2, this.size / 2);
                    ct.lineTo(this.size / 2, this.size);
                    ct.closePath();
                    ct.stroke();
                    ct.restore();
                }
                if (this.routeType[i] == 4) {
                    ct.save();
                    ct.translate(this.x * this.size, this.y * this.size);
                    ct.beginPath();
                    ct.lineWidth = "3";
                    ct.strokeStyle = "#e21609";
                    ct.moveTo(this.size / 2, this.size / 2);
                    ct.lineTo(0, this.size / 2);
                    ct.closePath();
                    ct.stroke();
                    ct.restore();
                }
                if (this.routeType[i] == 6) {
                    ct.save();
                    ct.translate(this.x * this.size, this.y * this.size);
                    ct.beginPath();
                    ct.lineWidth = "3";
                    ct.strokeStyle = "#e21609";
                    ct.moveTo(this.size / 2, this.size / 2);
                    ct.lineTo(this.size, this.size / 2);
                    ct.closePath();
                    ct.stroke();
                    ct.restore();
                }
                if (this.routeType[i] == 8) {
                    ct.save();
                    ct.translate(this.x * this.size, this.y * this.size);
                    ct.beginPath();
                    ct.lineWidth = "3";
                    ct.strokeStyle = "#e21609";
                    ct.moveTo(this.size / 2, this.size / 2);
                    ct.lineTo(this.size / 2, 0);
                    ct.closePath();
                    ct.stroke();
                    ct.restore();
                }
            }
        }
        return Square;
    })();


    $(function () {

        let canvas = null;
        let ct = null;
        let data = initData(10, 10);
        let type = 0;

        initCanvas(data);


        //初始化data
        function initData(xMax, yMax) {
            let data = [];
            for (let x = 0; x < xMax; x++) {
                let xData = [];
                data.push(xData);
                for (let y = 0; y < yMax; y++) {
                    xData.push(new Square(x, y, SIZE));
                }
            }
            return data;
        }

        //初始化模型
        function initCanvas(data) {
            if (data == null || data.length == 0) {
                return;
            }
            let x = data.length;
            let y = data[0].length;

            canvas = $("<canvas>").css({border: "2px solid #d3d3d3"}).attr("width", SIZE * x).attr("height", SIZE * y);

            $("#canvasWrap").append(canvas);
            $("#canvasWrap").width(canvas.width());
            ct = canvas[0].getContext("2d");

            for (let x = 0; x < data.length; x++) {
                for (let y = 0; y < data[x].length; y++) {
                    drawBlock(data[x][y]);
                }
            }
        }

        function refresh(param) {
            var dat = param || data;

            ct.clearRect(0, 0, canvas.width(), canvas.height());
            for (let x = 0; x < dat.length; x++) {
                for (let y = 0; y < dat[x].length; y++) {
                    drawBlock(dat[x][y]);
                }
            }
        }

        function drawBlock(square) {
            square.drawSquare(ct);
        }

        function bindClick(e) {
            let x = parseInt(e.offsetX / SIZE);
            let y = parseInt(e.offsetY / SIZE);

            if (type == 0) {
                data[x][y].type = 0;
                refresh();
                return;
            }

            if (data[x][y].type != 0) {
                return;
            }

            if (type == 2 || type == 3) {
                for (let x = 0; x < data.length; x++) {
                    for (let y = 0; y < data[x].length; y++) {
                        if (data[x][y].type == type) {
                            data[x][y].type = 0;
                        }
                    }
                }
            }

            data[x][y].type = type;
            refresh();
            return;

        }

        canvas.on("click", bindClick);


        $(".J_settype").on("click", function () {
            type = $(this).data("type");
        });

        $(".J_cal").on("click", function () {
            lessRoad(data);
        });

        //求最短路径 data 二维数组
        function lessRoad(data) {
            //对象
            /*
             *
             *
             */

            //1.找到起点 终点
            let startPoint = null;
            let endPoint = null;
            for (let x = 0; x < data.length; x++) {
                for (let y = 0; y < data[x].length; y++) {
                    if (data[x][y].type == 2) {
                        startPoint = data[x][y];
                    } else if (data[x][y].type == 3) {
                        endPoint = data[x][y];
                    }
                }
            }

            if(startPoint == null || endPoint == null){
                return;
            }
            //2.从起点开始寻找可走的路线，并且创建路径
            let roadList = [];
            let startRoad = new Road(data);
            startRoad.addNode(startPoint);

            roadList.push(startRoad);

            let checkList = checkRoadEnd(roadList);
            let step = 0;
            do {
                let newRoadList = [];
                for (let i = 0; i < roadList.length; i++) {
                    let list = roadList[i].next();
                    if (list != null && list.length > 0) {
                        for (let ii = 0; ii < list.length; ii++) {
                            newRoadList.push(list[ii]);
                        }
                    }
                }

                roadList = newRoadList;

                if(roadList.length == 0){
                    break;
                }
                checkList = checkRoadEnd(roadList);
            } while (checkList.length == 0 && ++step < 1000);
            console.log("step=" + step);

            setRoadWay(checkList[0].list);
            refresh();
        }

        function setRoadWay(road) {
            for (let x = 0; x < data.length; x++) {
                for (let y = 0; y < data[x].length; y++) {
                    data[x][y].routeType = [];
                }
            }

            for (let i = 1; i < road.length; i++) {
                let preNode = road[i - 1];
                let nowNode = road[i];
                if (nowNode.x - preNode.x == 1) {
                    data[preNode.x][preNode.y].routeType.push(6);
                    data[nowNode.x][nowNode.y].routeType.push(4);
                }
                if (nowNode.x - preNode.x == -1) {
                    data[preNode.x][preNode.y].routeType.push(4);
                    data[nowNode.x][nowNode.y].routeType.push(6);
                }
                if (nowNode.y - preNode.y == 1) {
                    data[preNode.x][preNode.y].routeType.push(2);
                    data[nowNode.x][nowNode.y].routeType.push(8);
                }
                if (nowNode.y - preNode.y == -1) {
                    data[preNode.x][preNode.y].routeType.push(8);
                    data[nowNode.x][nowNode.y].routeType.push(2);
                }
            }
        }
    });



    function checkRoadEnd(roadList) {
        let x = [];
        for (let i = 0; i < roadList.length; i++) {
            if (roadList[i].isEnd) {
                x.push(roadList[i]);
            }
        }
        return x;
    }

    var Road = (function () {
        let Road = function (data) {
            this.list = [];
            this.map = {};
            this.data = data;
            this.isEnd = false;
        }

        Road.prototype.addNode = function (node) {
            if (node == null) {
                return;
            }
            this.list.push(node);
            this.map[node.x + "-" + node.y] = node;
        }


        Road.prototype.next = function () {
            let roadList = [];
            let p = this.list[this.list.length - 1];

            let node = null;
            if (this.data[p.x] != null) {
                // 2
                node = checkNode(this.data[p.x][p.y + 1], this);
                if (node != null) {
                    let newRoad = getNewRoad(node, this.data, this);
                    if (node.type == 3) {
                        newRoad.isEnd = true;
                    }
                    roadList.push(newRoad);
                }

                // 8
                node = checkNode(this.data[p.x][p.y - 1], this);
                if (node != null) {
                    let newRoad = getNewRoad(node, this.data, this);
                    if (node.type == 3) {
                        newRoad.isEnd = true;
                    }
                    roadList.push(newRoad);
                }
            }
            // 4
            if (this.data[p.x - 1] != null) {
                node = checkNode(this.data[p.x - 1][p.y], this);
                if (node != null) {
                    let newRoad = getNewRoad(node, this.data, this);
                    if (node.type == 3) {
                        newRoad.isEnd = true;
                    }
                    roadList.push(newRoad);
                }
            }
            // 6
            if (this.data[p.x + 1] != null) {
                node = checkNode(this.data[p.x + 1][p.y], this);
                if (node != null) {
                    let newRoad = getNewRoad(node, this.data, this);
                    if (node.type == 3) {
                        newRoad.isEnd = true;
                    }
                    roadList.push(newRoad);
                }
            }

            return roadList;
        }

        function getNewRoad(node, data, oldRoad) {
            var road = new Road(data);
            road.map = oldRoad.map;
            for (let i = 0; i < oldRoad.list.length; i++) {
                road.addNode(oldRoad.list[i]);
            }
            road.addNode(node);
            return road;
        }

        function checkNode(node, load) {
            if (node == null) {
                return null;
            }

            if (load.map[node.x + "-" + node.y] != null) {
                return null;
            }

            if (node.type == 1) {
                return null;
            }

            return node;
        }

        return Road;
    })();

</script>
</body>
</html>